#
# @lc app=leetcode.cn id=32 lang=python3
#
# [32] 最长有效括号
#

# @lc code=start
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # dp[i]以第i个字符结尾的子串的有效括号子串长度
        # dp[0]=False
        # dp[i]=?
        n = len(s)
        dp = [0]*n
        max_len = 0
        # 1
        for i in range(1, n): # [1,n-1]
            if s[i] == ")":
                # 找对应左括号的位置
                idx = i-dp[i-1]-1
                if idx >=0 and s[idx]=='(':
                    dp[i] = dp[i-1] + 2
                    # 左括号的左边还有字符串
                    if idx-1>0:
                        dp[i] += dp[idx-1]
                    max_len = max(max_len, dp[i])
            # print(f's[{i}]={s[i]}, dp[{i}]={dp[i]}')
        
        return max_len


# @lc code=end

